// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
#include <iostream>
#include <vector>


using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int minPrice = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] - minPrice > profit) {
                profit = prices[i] - minPrice;
            } 
            if (minPrice > prices[i]) {
                minPrice = prices[i];
            }
        }
        return profit;
    }

    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        int minPrice = prices[0];   
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            profit = max(profit, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        return profit;
    }
};

int main() {
    Solution so;
    vector<int> nums = { 7,1,5,3,6,4 };
    int a = so.maxProfit(nums);
    cout << a << endl;
    return 0;
}